package jparchess.engine;

import java.util.ArrayList;

public class Search {
	
	public GameLine gameLine;
	public	MoveGenerator moveGenerator;
	public	MoveMaker moveMaker;
	public	Evaluator evaluator;
	public int perftCaptures = 0;
	public int perftCastling = 0;
	public int perftEnPassant = 0;
	public int perftChecks = 0;
	public Move bestMove;
	public int localBestMoveScore;
	public int absBestMoveScore;
	public int searchDepth;
	

	public int[] triangularLength;
    public Move[][] triangularArray;
	public int searchNodes;
	
	public Search(Board board, GameLine gameLine) {
		moveGenerator = new MoveGenerator();
		moveMaker = new MoveMaker();
		evaluator = new Evaluator(board);
		
		board.startPosition();
		moveGenerator.setBoard(board);
		moveGenerator.createKingAttacks();
		moveGenerator.createKnightAttacks();
		moveMaker.setBoard(board);
		moveMaker.setGameLine(gameLine);
		
		triangularLength = new int[D.MAX_PLY];
		triangularArray = new Move[D.MAX_PLY][D.MAX_PLY];
	}
	
	public void setMoveGen(MoveGenerator moveGen) {
		this.moveGenerator = moveGen;
	}
	
	public Move think(int searchDepth) {
		   searchNodes = 0;
	       absBestMoveScore = alphabetapvs(0, searchDepth, -9999, 9999);
	       return (triangularArray[0][0]);
	}
	
	
	public int alphabetapvs(int ply, int depth, int alpha, int beta)
	{
		 if (depth == 0) {
			 int eval = evaluator.basicEval();
			 if (evaluator.board.sideToMove == D.WHITE_TO_MOVE) return eval;
			 else return -eval;
		 }

	       // PV search 
	       int i, j, movesfound, val;
	       triangularLength[ply] = ply;       
	       movesfound = 0;
	       
	       moveGenerator.generateMoves();
		    ArrayList<Move> moveList = (ArrayList<Move>) moveGenerator.moveList.clone();
			for (Move move : moveList) {
				moveMaker.doMove(move);
				searchNodes++;
				
				 if (movesfound != 0)
                 {
                        val = -alphabetapvs(ply+1, depth-1, -alpha-1, -alpha);
                if ((val > alpha) && (val < beta))
                        {
                               val = -alphabetapvs(ply+1, depth - 1, -beta, -alpha);   // In case of failure, proceed with normal alphabeta       
                        }
                 }
                  else val = -alphabetapvs(ply+1, depth-1, -beta, -alpha);          // Normal alphabeta
				 moveMaker.undoMove(move);
                 if (val >= beta)
                 {
                        return beta;
                 }
                 if (val > alpha)
                 {
                        alpha = val;                                                      // both sides want to maximize from *their* perspective
                        movesfound++;
                        triangularArray[ply][ply] = move;                                  // save this move
                        for (j = ply + 1; j < triangularLength[ply + 1]; j++)
                        {
                               triangularArray[ply][j] = triangularArray[ply+1][j];   // and append the latest best PV from deeper plies
                        }
                        triangularLength[ply] = triangularLength[ply + 1];
//                        if (!ply)
//                        {
//                              // msStop = timer.getms();
//                               displaySearchStats(2, depth, val);
//                        }
                 }
				
			}
		return alpha;
//	       for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
//	       {
//	              makeMove(moveBuffer[i]);
//	              {
//	                     if (!isOtherKingAttacked())
//	                     {
//	                           //inodes++;
//	                           //if (!ply) displaySearchStats(3, ply, i);
//	                           if (movesfound)
//	                           {
//	                                  val = -alphabetapvs(ply+1, depth-1, -alpha-1, -alpha);
//	                          if ((val > alpha) && (val < beta))
//	                                  {
//	                                         val = -alphabetapvs(ply+1, depth - 1, -beta, -alpha);   // In case of failure, proceed with normal alphabeta       
//	                                  }
//	                           }
//	                            else val = -alphabetapvs(ply+1, depth-1, -beta, -alpha);          // Normal alphabeta
//	                           unmakeMove(moveBuffer[i]);
//	                           if (val >= beta)
//	                           {
//	                                  return beta;
//	                           }
//	                           if (val > alpha)
//	                           {
//	                                  alpha = val;                                                      // both sides want to maximize from *their* perspective
//	                                  movesfound++;
//	                                  triangularArray[ply][ply] = moveBuffer[i];                                  // save this move
//	                                  for (j = ply + 1; j < triangularLength[ply + 1]; j++)
//	                                  {
//	                                         triangularArray[ply][j] = triangularArray[ply+1][j];   // and append the latest best PV from deeper plies
//	                                  }
//	                                  triangularLength[ply] = triangularLength[ply + 1];
//	                                  if (!ply)
//	                                  {
//	                                         msStop = timer.getms();
//	                                         displaySearchStats(2, depth, val);
//	                                  }
//	                           }
//	                     }
//	                     else unmakeMove(moveBuffer[i]);
//	              }
//	       }
//	       return alpha;
	}
	
//	int Quiesce( int alpha, int beta ) {
//	    int stand_pat = Evaluate();
//	    if( stand_pat >= beta )
//	        return beta;
//	    if( alpha < stand_pat )
//	        alpha = stand_pat;
//	 
//	    until( every_capture_has_been_examined )  {
//	        MakeCapture();
//	        score = -Quiesce( -beta, -alpha );
//	        TakeBackMove();
//	 
//	        if( score >= beta )
//	            return beta;
//	        if( score > alpha )
//	           alpha = score;
//	    }
//	    return alpha;
//	}
	
	public int quis(int alpha, int beta)
	{
		int eval = evaluator.basicEval();
		if (evaluator.board.sideToMove == D.BLACK_TO_MOVE) eval = -eval;
		
		if (eval >= beta) 
			return beta;
		if ( alpha < eval )
			alpha = eval;
		
	    moveGenerator.generateMoves();
	    ArrayList<Move> moveList = (ArrayList<Move>) moveGenerator.moveList.clone();
		for (Move move : moveList) {
			if (move.captured != D.EMPTY) {
				moveMaker.doMove(move);
				eval = -quis(-beta, -alpha);
				moveMaker.undoMove(move);
				
				if (eval >= beta)
					return beta;
				if (eval > alpha)
					alpha = eval;
			}
		}
		return alpha;
	}
	
	public int pvSearch( int alpha, int beta, int depth ) {
		int score;
		if( depth == 0 ) return quis( alpha, beta );
		boolean bSearchPv = true;
	    moveGenerator.generateMoves();
	    ArrayList<Move> moveList = (ArrayList<Move>) moveGenerator.moveList.clone();
	    for (Move move : moveList) {
	    	moveMaker.doMove(move);
			
		      if ( bSearchPv ) {
		         score = -pvSearch(-beta, -alpha, depth - 1);
		      } 
		      else {
		         score = -pvSearch(-alpha-1, -alpha, depth - 1);
		         if ( score > alpha ) // in fail-soft ... && score < beta ) is common
		            score = -pvSearch(-beta, -alpha, depth - 1); // re-search
		      }
		      
			  moveMaker.undoMove(move);
		      if( score >= beta )
		         return beta;   // fail-hard beta-cutoff
		      if( score > alpha ) {
		         alpha = score; // alpha acts like max in MiniMax
		         bSearchPv = false;  // *1)
		      }
		      
		      // save move
              if (depth == 4) bestMove = move;
		   }  // end for
		 return alpha; // fail-hard
	}
	
		public int negascout(int depth, int alpha, int beta) {
			if (depth == 0) {
				//if (evaluator.board.sideToMove == D.WHITE_TO_MOVE) return +evaluator.basicEval() ;
				//else return -evaluator.basicEval() ;
				return quis(alpha, beta);
			}
            int localAlpha = 0;
            int score = 0;
            moveGenerator.generateMoves();
            // display
            //moveGenerator.displayMoves();
            localAlpha = -9999;
            ArrayList<Move> moveList = (ArrayList<Move>) moveGenerator.moveList.clone();
            for (Move move : moveList) {
                    moveMaker.doMove(move);
                    score = -negascout(depth-1, -beta, -alpha);
                    moveMaker.undoMove(move);
                    if (score > localAlpha) {
                            if (score > alpha) 
                                    alpha = score;
                            localAlpha = score;
                            if (alpha >= beta)
                                    break;
                                    
                            // save move
                            if (depth == 2) bestMove = move;
                    }
            }
            return localAlpha;
            
	}
	
	public int negamax(int depth) {
		if (depth == 0) {
			if (evaluator.board.sideToMove == D.WHITE_TO_MOVE) return +evaluator.basicEval() ;
			else return -evaluator.basicEval() ;
		}
		
		    int max = -9999;
		    moveGenerator.generateMoves();
		    ArrayList<Move> moveList = (ArrayList<Move>) moveGenerator.moveList.clone();
			for (Move move : moveList) {
				moveMaker.doMove(move);
		        localBestMoveScore = -negamax( depth - 1 );
				//D.logSearch(move, depth,localBestMoveScore);
			    moveMaker.undoMove(move);
		        if( localBestMoveScore >= max ) {		        	
		        	max = localBestMoveScore;
		        	if (depth == 2) bestMove = move;
		        }
		            
		    }
		    return max;
	}
		

	public int perft(int ply, int depth) {
		int retVal = 0;
		if (depth == 0) return 1;
				
		moveGenerator.generateMoves();
		
		//if (ply == 2) moveGenerator.displayMoves();
		
		ArrayList<Move> moveList = (ArrayList<Move>) moveGenerator.moveList.clone();
		for (Move move : moveList) {
			if (move.captured != 0) perftCaptures++;
			if (move.castling != 0) perftCastling++;
			if (move.captured == D.WHITE_KING || move.captured == D.BLACK_KING) perftChecks++;
			moveMaker.doMove(move);
			retVal += perft(ply + 1, depth - 1);
		    moveMaker.undoMove(move);
		}
		
		return retVal;
	}
	
	
}
